package g

/*
 * @lc app=leetcode.cn id=23 lang=golang
 *
 * [23] 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
*/

// ListNode Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	var headNodes []*ListNode
	for i := 0; i < len(lists); i++ {
		if lists[i] != nil {
			headNodes = insertSort(headNodes, lists[i])
		}
	}
	newList := &ListNode{}
	p := newList
	for len(headNodes) > 0 {
		p.Next = headNodes[0]
		p = p.Next
		if headNodes[0].Next == nil {
			headNodes = headNodes[1:]
		} else {
			headNodes = insertSort(headNodes[1:], headNodes[0].Next)
		}
		p.Next = nil
	}
	return newList.Next
}

// insertSort，在已经有序的数组，插入一个新数据。这里使用冒泡，可以使用二分会更快一些
func insertSort(headNodes []*ListNode, node *ListNode) []*ListNode {
	headNodes = append(headNodes, node)
	for i := len(headNodes) - 2; i >= 0; i-- {
		if headNodes[i+1].Val >= headNodes[i].Val {
			break
		} else {
			headNodes[i], headNodes[i+1] = headNodes[i+1], headNodes[i]
		}
	}
	return headNodes
}

// @lc code=end
